/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.acworks.acroute.v2.impl;

import com.acworks.acroute.v2.Arc;
import com.acworks.acroute.v2.ArcDirectionType;
import com.acworks.acroute.v2.Graph;
import com.acworks.acroute.v2.Node;
import com.acworks.acroute.v2.Path;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 *
 * @author nikita
 */
public class GraphUtil {

    static public Node findById(Set<Node> nodes, int id) {
        assert nodes != null;
        if (id < 0) {
            return null;
        }

        for (Node n : nodes) {
            if (n.getId() == id) {
                return n;
            }
        }
        return null;
    }

    public static boolean isClosedNonHamiltonianCircuit(Set<Arc> unusedArcs, Set<Node> visitedNodes, Node currentNode, Graph g) {
        assert unusedArcs != null;
        assert visitedNodes != null;
        assert currentNode != null;
        assert g != null;

        boolean closedCircuit = false;

        while (!unusedArcs.isEmpty()) {

            if (visitedNodes.contains(currentNode)) {
                closedCircuit = true;
                break;
            } else {
                //count currentNode as visited
                visitedNodes.add(currentNode);
            }

            Arc currentArc = null;

            //find arc starting at currentNode
            Iterator<Arc> arcIter = unusedArcs.iterator();
            while (arcIter.hasNext()) {
                Arc a = arcIter.next();
                if (currentNode.equals(a.getSourceNode()) || (a.getType() == ArcDirectionType.UNDIRECTED && currentNode.equals(a.getTargetNode()))) {
                    currentArc = a;
                    arcIter.remove();
                    break;
                }
            }

            //if there's no arc starting at current node -> path is terminated
            if (currentArc == null) {
                closedCircuit = false;
                break;
            } else {
                //advance to targetNode (or the other node i
                if (currentArc.getType() == ArcDirectionType.UNDIRECTED) {
                    currentNode = currentArc.getSourceNode().equals(currentNode) ? currentArc.getTargetNode() : currentArc.getSourceNode();
                } else {
                    currentNode = currentArc.getTargetNode();
                }
            }
        }

        //TODO HACK?
        if (unusedArcs.isEmpty() && !closedCircuit) {
            closedCircuit = visitedNodes.contains(currentNode);
        }

        //terminating at startNode?
        boolean finishedAtStartNode = currentNode.equals(g.getStartingNode());

        return closedCircuit && !(finishedAtStartNode && visitedNodes.equals(g.getNodes()));
    }

    /**
     *
     * @param potentialClosedCircuit
     * @param nodes
     * @return true only if any subset of given arcs forms a closed circuit that does not visit each
     * node in 'allNodes' exactly once. return false otherwise
     */
    public static boolean isClosedNonHamiltonianCircuit(final Set<Arc> arcs, Graph g) {
        assert g != null;
        assert arcs != null;

        if (arcs.isEmpty()) {
            return false;
        }

        Set<Arc> unusedArcs = new HashSet<Arc>(arcs);
        Set<Node> visitedNodes = new HashSet<Node>();
        Node currentNode = g.getStartingNode();

        return isClosedNonHamiltonianCircuit(unusedArcs, visitedNodes, currentNode, g);
    }

    public static Arc findConnectingArc(Node n1, Node n2, Set<Arc> arcs) {
        assert n1 != null;
        assert n2 != null;
        assert arcs != null;
        assert !n1.equals(n2);

        for (Arc arc : arcs) {
            if ((arc.getSourceNode().equals(n1) || arc.getSourceNode().equals(n2)) &&
                    (arc.getTargetNode().equals(n1) || arc.getTargetNode().equals(n2))) {
                return arc;
            }
        }
        return null;
    }

    /**
     *
     * @param arcs
     * @return collection of Nodes connected by given arcs
     */
    public static Set<Node> getNodes(Set<Arc> arcs) {
        assert arcs != null;
        Set<Node> nodes = new HashSet<Node>();
        for (Arc arc : arcs) {
            nodes.add(arc.getSourceNode());
            nodes.add(arc.getTargetNode());
        }
        return nodes;
    }

    private GraphUtil() {
    }

    /**
     *
     * @return a collection of directed arcs that must be present in every Hamiltonian Path
     * containing given partialPath.
     */
    static public Set<Arc> findRequiredArcs(Graph g, Path p) {
        assert g != null;
        assert p != null;

        Set<Arc> required = new HashSet<Arc>();

        final List<Node> pathNodes = p.getPathNodes();
        //arcs connecting Nodes to form partialPath are all required
        for (int i = 0; i < pathNodes.size(); i++) {
            if (i + 1 < pathNodes.size()) {
                Node srcNode = pathNodes.get(i);
                Arc arc = findConnectingArc(srcNode, pathNodes.get(i + 1), g.getArcs());
                assert arc.getType() == ArcDirectionType.UNDIRECTED || arc.getSourceNode().equals(srcNode);
                required.add(arc);
            }
        }

        //apply R1 and R2 deduction rules:
        //if a node has only one directed arc leaving(entering) (AND NO UNDIRECTED ARCS?) -> that arc's required
        //if a node has only two arcs incident -> both are required
        for (Node node : g.getNodes()) {

            //TODO: may result in redundant adds for arcs already added above, but the op's idempotent

            Set<Arc> terminatingArcs = g.getIncidentDirectedArcs(node, false);
            Set<Arc> originatingArcs = g.getIncidentDirectedArcs(node, true);
            Set<Arc> undirectedArcs = g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED);

            if (terminatingArcs.size() == 1 && undirectedArcs.isEmpty()) {
                Arc arc = terminatingArcs.iterator().next();
                required.add(arc);
            }

            if (originatingArcs.size() == 1 && undirectedArcs.isEmpty()) {
                Arc arc = originatingArcs.iterator().next();
                required.add(arc);
            }

            if (originatingArcs.size() + terminatingArcs.size() + undirectedArcs.size() == 2) {
                required.addAll(originatingArcs);
                required.addAll(terminatingArcs);
                required.addAll(undirectedArcs);
            }
        }

        return required;
    }

    /**
     * A1. If a vertex has a required directed arc entering (leaving), then all incident undirected
     * arcs are assigned the direction leaving (entering) that vertex.
     *
     * <p>
     * A2. If a vertex has a required undirected arc incident, and all other incident arcs are
     * leaving (entering) the vertex, then the required arc is assigned the direction entering
     * (leaving) the vertex.
     *
     * @return collection of arcs whose directions were actually changed
     */
    public static Set<Arc> updateArcDirections(Graph g, Set<Arc> requiredArcs) {
        assert g != null;
        assert requiredArcs != null;

        Set<Arc> alteredArcs = new HashSet<Arc>();

        for (Node node : g.getNodes()) {
            //find required originating arcs
            Set<Arc> requiredOriginatingArcs = new HashSet<Arc>(g.getIncidentDirectedArcs(node, true));
            requiredOriginatingArcs.retainAll(requiredArcs);

            //if required originating arc exists -> make all incident undirected arcs directed, terminating at this node
            if (!requiredOriginatingArcs.isEmpty()) {
                for (Arc undirectedArc : new HashSet<Arc>(g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED))) {

                    Node originNode = undirectedArc.getSourceNode().equals(node) ? undirectedArc.getTargetNode() : undirectedArc.getSourceNode();
                    undirectedArc.makeDirected(originNode);
                    alteredArcs.add(undirectedArc);
                }

                //assert g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED).isEmpty();
            }


            //find required terminating arcs
            Set<Arc> requiredTerminatingArcs = new HashSet<Arc>(g.getIncidentDirectedArcs(node, false));
            requiredTerminatingArcs.retainAll(requiredArcs);

            //if required terminating arc exists -> make all incident undirected arcs directed, originating at this node
            if (!requiredTerminatingArcs.isEmpty()) {
                for (Arc undirectedArc : new HashSet<Arc>(g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED))) {
                    undirectedArc.makeDirected(node);
                    alteredArcs.add(undirectedArc);
                }

                //assert g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED).isEmpty();
            }

            //find required undirected arcs
            Set<Arc> requiredUndirectedArcs = new HashSet<Arc>(g.getIncidentArcs(node, ArcDirectionType.UNDIRECTED));
            boolean allUndirectedRequired = !requiredUndirectedArcs.retainAll(requiredArcs);

            if (allUndirectedRequired && requiredUndirectedArcs.size() == 1) {

                Arc soleRequiredUndirectedArc = requiredUndirectedArcs.iterator().next();

                if (!g.getIncidentDirectedArcs(node, false).isEmpty() && g.getIncidentDirectedArcs(node, true).isEmpty()) {

                    if (soleRequiredUndirectedArc.makeDirected(node)) {
                        alteredArcs.add(soleRequiredUndirectedArc);
                    }

                } else if (g.getIncidentDirectedArcs(node, false).isEmpty() && !g.getIncidentDirectedArcs(node, true).isEmpty()) {

                    Node originNode = soleRequiredUndirectedArc.getSourceNode().equals(node) ? soleRequiredUndirectedArc.getTargetNode() : soleRequiredUndirectedArc.getSourceNode();
                    if (soleRequiredUndirectedArc.makeDirected(originNode)) {
                        alteredArcs.add(soleRequiredUndirectedArc);
                    }
                }
            }
        }

        return alteredArcs;
    }

    /**
     * D. Deleted edge rules:
     *
     * <p>
     * D1. If a vertex has two required arcs incident, then all undecided arcs incident may
     * be deleted.
     *
     * <p>
     * D2. If a vertex has a required directed arc entering (leaving), then all undecided
     * directed arcs entering (leaving) may be deleted.
     *
     * <p>
     * D3. Delete any arc which forms a closed circuit with required arcs, unless it completes
     * the Hamilton circuit.
     *
     * @return collection of Arcs that can be safely deleted
     */
    public static Set<Arc> findUnneededArcs(Graph g, Set<Arc> requiredArcs) {
        assert g != null;
        assert requiredArcs != null;

        Set<Arc> unneededArcs = new HashSet<Arc>();

        for (Node node : g.getNodes()) {
            Set<Arc> allIncidentArcs = g.getIncidentArcs(node, null);

            Set<Arc> requiredIncidentArcs = new HashSet<Arc>(allIncidentArcs);
            requiredIncidentArcs.retainAll(requiredArcs);

            //If a vertex has two required arcs incident --> delete all others
            if (requiredIncidentArcs.size() == 2) {
                allIncidentArcs.removeAll(requiredIncidentArcs);
                unneededArcs.addAll(allIncidentArcs);
            }

            //If a vertex has a required directed arc entering (leaving), then all undecided
            //directed arcs entering (leaving) may be deleted.
            Set<Arc> originatingArcs = g.getIncidentDirectedArcs(node, true);
            if (!Collections.disjoint(originatingArcs, requiredArcs)) {
                originatingArcs.removeAll(requiredArcs);
                unneededArcs.addAll(originatingArcs);
            }

            Set<Arc> terminatingArcs = g.getIncidentDirectedArcs(node, false);
            if (!Collections.disjoint(terminatingArcs, requiredArcs)) {
                terminatingArcs.removeAll(requiredArcs);
                unneededArcs.addAll(terminatingArcs);
            }
        }

        /*
         * Delete any arc which forms a closed circuit with required arcs, unless it completes
         * the Hamilton circuit.
         */
//        assert !isClosedNonHamiltonianCircuit(requiredArcs, g); //safe to remove

        final Set<Node> visitedNodes = getNodes(requiredArcs);

        Set<Arc> potentialClosedCircuit = new HashSet<Arc>(requiredArcs);
        Arc prevNonRequiredArc = null;
        Set<Arc> nonRequiredArcs = new HashSet<Arc>(g.getArcs());
        nonRequiredArcs.removeAll(requiredArcs);
        for (Arc nonRequiredArc : nonRequiredArcs) {
            //nonRequiredArc that may for a closed circuit must
            // connect nodes already incident to requiredArcs
            if (visitedNodes.contains(nonRequiredArc.getSourceNode()) && visitedNodes.contains(nonRequiredArc.getTargetNode())) {

                if (prevNonRequiredArc != null) {
                    potentialClosedCircuit.remove(prevNonRequiredArc);
                }
                potentialClosedCircuit.add(nonRequiredArc);
                prevNonRequiredArc = nonRequiredArc;                
                if (isClosedNonHamiltonianCircuit(potentialClosedCircuit, g)) {
                    unneededArcs.add(nonRequiredArc);
                }
            }
        }
//        Arc prevNonRequiredArc = null;
//        Set<Arc> potentialClosedCircuit = new HashSet<Arc>(requiredArcs);
//        for (Arc nonRequiredArc : nonRequiredArcs) {
//
//            //nonRequiredArc forms a closed circuit if both incident nodes
//            //are have already been visited by some of the 'requiredArcs'
//            if (prevNonRequiredArc != null) {
//                potentialClosedCircuit.remove(prevNonRequiredArc);
//            }
//            potentialClosedCircuit.add(nonRequiredArc);
//            prevNonRequiredArc = nonRequiredArc;
//            if (isClosedNonHamiltonianCircuit(potentialClosedCircuit, g)) {
//                unneededArcs.add(nonRequiredArc);
//            }
//        }

        return unneededArcs;
    }
}
